package com.chao.stucture.list;

import java.util.HashMap;

/**
 * @author : Rookie
 * @description : 不带头单链表相关操作
 * @date : 2022/3/13
 */
public class SingleLinkedList<E> {

    /**
     * 头指针
     */
    private Node<E> head;
    /**
     * 链表大小
     */
    private int size;

    public SingleLinkedList() {
        this.size = 0;
        this.head = null;
    }

    /**
     * 节点内部类
     */
    static class Node<E> {
        /**
         * 下一节点
         */
        private Node<E> next;
        /**
         * 元素
         */
        private E element;

        public Node(E element) {
            this.element = element;
        }
    }

    private Boolean isEmpty() {
        return this.size == 0;
    }

    public int size() {
        return this.size;
    }

    /**
     * 尾插法
     * @param e 元素
     */
    public void addLast(E e) {
        Node<E> newNode = new Node<>(e);
        if (this.head == null) {
            this.head = newNode;
        } else {
            Node<E> currNode = head;
            while (currNode.next != null) {
                currNode = currNode.next;
            }
            currNode.next = newNode;
        }
        this.size ++;
    }

    /**
     * 头插法
     * @param e 元素
     */
    public void addFirst(E e) {
        Node<E> newNode = new Node<>(e);
        if (this.head != null) {
            newNode.next = this.head;
        }
        this.head = newNode;
        this.size ++;
    }

    /**
     * 在链表指定位置插入
     * @param position 指定位置
     * @param element 元素
     * @return
     */
    public Boolean add(int position, E element) {
        Node<E> newNode = new Node<>(element);
        //判断是否越界
        if(position < 0 || position > this.size) {
            return false;
        }
        //判断是否插入头部
        if (position == 0) {
            addFirst(element);
        } else {
            //遍历链表
            //当前节点
            Node<E> currNode = this.head;
            //上一节点
            Node<E> preNode = null;
            //索引
            int index = 0;
            while (index < position) {
                preNode = currNode;
                currNode = currNode.next;
                index ++;
            }
            preNode.next = newNode;
            if (currNode != null) {
                newNode.next = currNode;
            }
        }
        this.size ++;
        return true;
    }

    /**
     * 清空链表
     */
    public void clear() {
        this.head = null;
        this.size = 0;
    }

    /**
     * 删除指定位置的结点
     * @param position
     */
    public void remove(int position) {
        //判断是否越界
        if(position < 0 || position > this.size) {
            throw new RuntimeException("链表越界！");
        }
        Node<E> currNode = this.head;
        Node<E> preNode = null;
        if (position == 0) {
            this.head = currNode.next;
        } else {
            int index = 0;
            while (index < position) {
                preNode = currNode;
                currNode = currNode.next;
                index ++;
            }
            preNode.next = currNode.next;
        }
        this.size --;
    }

    /**
     * 移除链表中的指定元素
     * @param element
     */
    public void remove(E element) {
        //如果头节点的值就是要移除的值
        if (this.head != null && this.head.element.equals(element)) {
            this.head = this.head.next;
        } else {
            // 处理非头部节点的删除
            Node<E> currNode = this.head,preNode = null;
            while (currNode != null) {
                if (currNode.element.equals(element)) {
                    if (preNode != null) {
                        preNode.next = currNode.next;
                    }
                } else {
                    // 记录当前节点
                    preNode = currNode;
                }
                // 继续向下遍历
                currNode = currNode.next;
            }
        }
        this.size --;
    }

    public E get(int i) {
        if (i < 0 || i >= this.size) {
            throw new RuntimeException("链表越界异常！");
        }
        Node<E> currNode = this.head;
        int index = 0;
        while (index < i) {
            currNode = currNode.next;
            index ++;
        }
        return currNode.element;
    }

    /**
     * 更新指定索引处元素的值
     * @param position 指定位置
     * @param element 值
     */
    public void update(int position, E element) {
        //判断是否越界
        if(position < 0 || position > this.size) {
            throw new RuntimeException("链表越界异常！");
        }
        int index = 0;
        Node<E> currNode = this.head;
        while (index < position) {
            currNode = currNode.next;
            index ++;
        }
        currNode.element = element;
    }

    public void display(){
        Node<E> currNode = head;
        StringBuilder sb = new StringBuilder();
        while (currNode != null){
            sb.append(currNode.element);
            if (currNode.next != null) {
                sb.append("->");
            }
            currNode = currNode.next;
        }
        System.out.println(sb);
    }

    public static void main(String[] args) {
        SingleLinkedList<String> singleLinkedList = new SingleLinkedList<>();
        singleLinkedList.addLast("A");
        singleLinkedList.addLast("B");
        singleLinkedList.addLast("C");
        singleLinkedList.addFirst("O");
        singleLinkedList.addFirst("R");
        singleLinkedList.addLast("P");
        singleLinkedList.add(5,"Q");
        singleLinkedList.display();

        String element = singleLinkedList.get(3);
        System.out.println();
        System.out.println("索引为" + 3 + "的元素是" + element);
        singleLinkedList.update(0,"S");
        singleLinkedList.display();
        singleLinkedList.remove("A");
        System.out.println("=======================================");
        singleLinkedList.display();
    }
}

